import java.util.PriorityQueue;

/**
 * 1753. 移除石子的最大得分
 * https://leetcode-cn.com/problems/maximum-score-from-removing-stones/
 */
public class Solutions_1753 {
    public static void main(String[] args) {
        int a = 2, b = 4, c = 6;  // output: 6
//        int a = 4, b = 4, c = 6;  // output: 7
//        int a = 1, b = 8, c = 8;  // output: 8

        int result = maximumScore(a, b, c);
        System.out.println(result);
    }

    /**
     * 解法二：数学法（0ms）
     * 存在规律：
     * 共两种情况
     * 1. 较小的两堆之和 <= 最大的一堆：则直接返回最小的两堆之和
     * 2. 较小的两堆之和 > 最大的一堆：则返回 (a + b + c) / 2
     */
    public static int maximumScore(int a, int b, int c) {
        if (a + b <= c) {
            return a + b;
        }
        if (b + c <= a) {
            return b + c;
        }
        if (a + c <= b) {
            return a + c;
        }
        return (a + b + c) / 2;
    }

    /**
     * 解法一：优先队列（91ms）
     * 每次取最大的两个数，分别减 1 后，再放回到优先队列中，直到有两个数为 0
     */
    public static int maximumScore2(int a, int b, int c) {
        // 大顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        queue.add(a);
        queue.add(b);
        queue.add(c);
        int res = 0;
        while (true) {
            int max = queue.poll();
            int mid = queue.poll();
            if (mid == 0) {
                return res;
            }
            res ++;
            queue.add(--max);
            queue.add(--mid);
        }
    }
}
